\input macros
\drafttrue
\tolerance=2500
\def\bookline{\CLOS\  Specification}
\def\chapline{Programmer Interface Concepts}

\beginChapter 1.{Common Lisp Object System Specification}%
{Programmer Interface Concepts}{Programmer Interface Concepts}

This document was written by Daniel G. Bobrow, Linda G. DeMichiel,\break
Richard P. Gabriel, Sonya E. Keene, Gregor Kiczales, and David A. Moon.

Contributors to this document include Patrick Dussud, Kenneth Kahn,\break
Jim Kempf, Larry Masinter, Mark Stefik,
Daniel L. Weinreb, and Jon L White.

\endTitlePage

\beginSection{Introduction}

This proposal presents a description of the standard Programmer
Interface for object-oriented programming in the \CLOS.    The first
chapter of this document describes the concepts of the \CLOS, and the
second gives an alphabetic list of the functions and macros that comprise
the \CLOS\ Programmer Interface.
A third chapter, ``The \CLOS\ Meta-Object Protocol,'' will describe how the
\CLOS\ can be customized to support other existing object-oriented
paradigms and to define new ones.

The fundamental objects of the \CLOS\ are classes, instances,
generic functions, and methods. 

A {\bit class\/} object determines the structure and behavior of a set
of other objects, which are called its {\bit instances}.  It is an important
feature of the \OS\ that every Common Lisp object is an {\bit
instance\/} of a class.  The class of an object determines the set of
operations that can be performed on the object.

A {\bit generic function} is a function whose behavior depends on the
classes or identities of the arguments supplied to it.  A generic
function object comprises a set of methods, a lambda-list, a method
combination type, and other information.  The methods define the
class-specific behavior and operations of the generic function.  Thus,
generic functions are objects that may be {\bit specialized} by the
definition of methods to provide class-specific operations.  A generic
function chooses one or more of the set of its methods based on the
classes of its arguments.

A generic function can be used in 
the same ways that an ordinary function can be used in Common Lisp; in
particular, a generic function can be used as an argument to {\bf
funcall} and {\bf apply} and stored in the function cell of a symbol.

The class-specific operations provided by generic functions are
themselves defined and implemented by {\bit methods}.  A method object
contains a method function, an ordered set of {\bit parameter specializers\/}
that specify when the given method is applicable, and an ordered set of {\bit
qualifiers\/} that are used by the method combination facility to
distinguish among methods.  Each required formal parameter of each
method has an associated parameter specializer, and the method is
expected to be invoked only on arguments that satisfy its parameter
specializers.

To summarize, a generic function is a function that contains or
encompasses a number of methods.  
When a generic function is invoked, the classes of its required arguments
determine which methods might be invoked.  The behavior of the generic
function results from which methods are selected for execution, the
order in which the selected methods are called, and how their values
are combined to produce the value or values of the generic function.
The {\bit method combination\/} facility controls the selection of
methods, the order in which they are run, and the values that are
returned by the generic function.  The \CLOS\ offers a default method
combination type that is appropriate for most user programs.  The
\CLOS\ also provides a facility for declaring new types of method
combination for programs that require them.

\endSection%{Introduction}

\beginSection{Classes}

A {\bit class\/} is an object that determines the structure and behavior 
of a set of other objects, which are called its {\bit instances}.   

A class can inherit structure and behavior from other classes.  
A class whose definition refers to other classes for the purpose of
inheriting from them is said to be a {\bit subclass\/} of each of
those classes.  The classes that are designated for purposes of
inheritance are said to be {\bit superclasses\/}
of the inheriting class.

A class can have a {\bit name}, which is a symbol. The function {\bf
class-name} takes a class object and returns its name. The name of an
anonymous class is {\bf nil}.  The function {\bf symbol-class} takes a
symbol and returns the class associated with that symbol. We say that a
class~$C$ has a {\bit proper name}~$S$ if $C=({\hbox{symbol-class}} S)$.
Notice that it is possible that $C\neq ({\hbox{symbol-class}}
({\hbox{class-name}} C))$.

We say that a class, $C\sub{1}$, is a {\bit direct superclass\/} of 
a class, $C\sub{2}$, if $C\sub{2}$ explicitly designates
$C\sub{1}$ as a superclass in its definition. 
We say that $C\sub{2}$ is a {\bit direct subclass\/} of $C\sub{1}$.  
We will say that a class 
$C\sub{n}$ is a {\bit superclass\/} of a class $C\sub{1}$ if there
exists a series of classes $C\sub{2},\ldots,C\sub{n-1}$ such that
$C\sub{i+1}$ is a direct superclass of $C\sub{i}$ for $1 \leq i<n$.
In this case, we say that $C\sub{1}$ is a {\bit subclass\/} of
$C\sub{n}$.  A class is considered neither a superclass nor a subclass of itself.  That 
is, if $C\sub{1}$ is a superclass of $C\sub{2}$, then $C\sub{1} \neq
C\sub{2}$.  We refer to the set of classes consisting of some given
class $C$ along with all of its superclasses as ``$C$ and its superclasses.''

When a class is defined, the order in which its direct superclasses
are mentioned in the defining form is important.  Each class has a
{\bit local precedence order\/}, which is a list consisting of the
class followed by its direct superclasses in the order mentioned
in the defining form.

Each class has a {\bit class precedence list}, which is a total ordering
on the set of the given class and its superclasses.  The total ordering
is expressed as a list ordered from most specific to least specific.
The class precedence list is used in several ways.  In general, more
specific classes can {\bit shadow}, or override, features that would
otherwise be inherited from less specific classes.  The method selection
and combination process uses the class precedence list to order methods
from most specific to least specific. 
 
A class precedence list is always consistent with the local precedence
order of each class in the list.  The classes in each local precedence
order appear within the class precedence list in the same order.  If
the local precedence orders are inconsistent with each other, no class
precedence list can be constructed, and an error will be signaled.
The class precedence list and its computation is discussed at
length in the section ``Determining the Class Precedence List.''

Classes are organized into a {\bit directed acyclic graph}.  There is
a distinguished class named {\bf t}.  The class {\bf t} has no
superclasses.  It is a superclass of every class except itself.

There is a mapping from the Common Lisp type space
into the Common Lisp Object System class space.  Many of the standard 
Common Lisp types specified in {\it Common Lisp: The Language\/} by Guy
L. Steele Jr.  have a corresponding class that has the same proper name as the 
type.  Some Common Lisp types do  
not have a corresponding class.   The integration of the type and class 
system is discussed later in this chapter.    

Classes are represented by first-class objects that are themselves 
instances of classes.
The class of the class of an object is termed the {\bit metaclass\/}
of that object.  When no misinterpretation is possible, we will also
use the term {\bit metaclass\/} to refer to a class that has instances
that are themselves classes.  The metaclass determines the form of
inheritance used by the classes that are its instances and the
representation of the instances of those classes.  The \CLOS\ provides
a default metaclass that is appropriate for most programs.  The
meta-object protocol will allow for defining and using new metaclasses.

\beginsubSection{Defining Classes}

The macro {\bf defclass} is used to define a new class.  The syntax for 
{\bf defclass} is given in Figure~2-1.   

The definition of a class includes:

\beginlist

\item{\bull} The name of the new class.

\item{\bull} The list of the direct superclasses of the new class. 

\item{\bull} A set of slot specifiers.  Each slot specifier includes the name of the  
slot and zero or more slot options.  A slot option pertains only to a
single slot.

\item{\bull} A set of class options.  Each class option pertains 
to the class as a whole.  
\endlist

The slot options and class options of the {\bf defclass} form allow for 
the following:

\beginlist

\item{\bull} Providing a default initial value form for a given slot.  

\item{\bull} Requesting that methods for appropriately named generic functions
be automatically generated for reading or writing one or more slots. 

\item{\bull} Controlling whether one copy of a given slot is
shared by instances or whether each instance has its own copy of that
slot.  

\item{\bull} Requesting that a constructor function be automatically
generated for making instances of the new class.

\item{\bull} Indicating that the instances of the class are to have a
metaclass other than the default.
\endlist 
\endsubSection%{Defining Classes}

\beginsubSection{Creating Instances of Classes}

The generic function {\bf make-instance} creates and returns a new
instance of a class.  The \OS\ provides a flexible means for specifying
how a new instance is to be initialized.  For example, it is possible to
specify the initial values for slots in newly-created instances, either by
giving an argument to {\bf make-instance} or by providing a default
initial value.  Further initialization activities can be performed by
methods written for generic functions that are part of the initialization
protocol.  The complete initialization protocol is described in the
section ``Object Creation and Initialization.''

\endsubSection%{Creating Instances of Classes}

\beginsubSection{Slots}

An object has zero or more named slots.  The slots of an object are
determined by the class of the object.  Each slot can hold one value.
The name of a slot is a symbol that can be used as a Common Lisp
variable name.

We define a {\bit local slot} to be a slot which is visible to exactly one
instance, namely the one in which the slot is allocated.  We define a
{\bit shared slot} to be a slot which is visible to a subset of the
instances of a given class and its subclasses.  Often this subset is the
same as the set of instances of the class and its subclasses, but a
smaller subset can result if a subclass redefines the slot.

The {\bf :allocation} slot option controls the kind of slot that is
defined.  If the value of the {\bf :allocation} slot option is {\bf
:instance}, a {\bit local slot\/} is created.
This is the most commonly
used kind of slot.  If the value of {\bf :allocation} is {\bf :class}, a
{\bit shared slot\/} is created.

In general, slots are inherited by subclasses.  That is, a slot defined
by a class is also a slot implicitly defined by any subclass
of that class unless the subclass explicitly shadows the slot
definition.  A class can also shadow some of the slot options declared
in the {\bf defclass} form of one of its superclasses by providing its
own description for that slot.  A detailed explanation of the inheritance
of slot options is given in the section ``Inheritance of Slots and
Slot Options.''

We say that a slot is {\bit accessible\/} in an instance of a class if
the slot is defined by the class of the instance or is inherited from 
a superclass of that class.  At most, one slot of a given name can be
accessible in an instance.

\endsubSection%{Slots}

\beginsubSection{Accessing Slots}

Slots can be accessed in two ways: by use of generic functions defined by
the {\bf defclass} form and by use of the primitive function 
{\bf slot-value}.   

The {\bf defclass} syntax allows for generating methods to
read and write slots.  If an {\bit accessor\/} is requested, a method
is automatically generated for reading the value of the slot, and a
{\bf setf} method for it is also generated.  If a {\bit reader\/} is
requested, a method is automatically generated for reading the value
of the slot, but no {\bf setf} method for it is generated.  
These methods are added to the appropriate generic functions.
Readers and accessors are implemented by using {\bf slot-value}.

Readers and accessors can be specified for individual slots or for all
slots.  When a reader or accessor is specified for an individual slot,
the name of the generic function is directly specified.  When readers
and accessors are requested for all slots, the names of the generic
functions are determined by combining a prefix and the individual slot
names.  It is possible to modify the behavior of these generic
functions by writing methods for them.

The function {\bf slot-value} can be used with any of the slot names
specified in the {\bf defclass} form to access a specific slot in an
object of the given class.  Note that {\bf slot-value} can be used to
read or write the value of a slot whether or not accessor
functions exist for that slot.  When {\bf slot-value} is used, no
methods for the accessors are called.

Sometimes it is convenient to access slots from within the body of a
method or a function.  The macro {\bf with-slots} can be used to set
up a lexical environment in which certain slots are lexically
available as if they were variables.  The macro {\bf with-slots}
enables one to specify whether the accessors or the function {\bf
slot-value} is to be used to access the slots.

\endsubSection%{Accessing Slots}
\endSection%{Classes}

\beginSection{Inheritance}

Inheritance is the key to program modularity within the \CLOS.  A typical
object-oriented program consists of several classes, each of which
defines some aspect of behavior.  New classes are defined by including
the appropriate classes as superclasses, thus gathering desired aspects
of behavior into one class.

A class can inherit slots and some {\bf defclass} options from 
its superclasses.  This section describes what
is inherited from superclasses and how a class can shadow an aspect
of inherited behavior.  
 
\beginsubSection{Inheritance of Methods}

A subclass inherits methods in the sense that any method applicable to
an instance of a class is also applicable to instances of any subclass
of that class (all other arguments to the method being the same).

The inheritance of methods acts the same way regardless of whether the
method was created by using {\bf defmethod} or by using one of the
{\bf defclass} options that cause methods to be generated
automatically.

The inheritance of methods is described in detail in the section
``Method Selection and Combination.''   

\endsubSection%{Inheritance of Methods}

\beginsubSection{Inheritance of Slots and Slot Options}

The set of the names of all slots accessible in an instance of a class
$C$ is the union of the sets of names of slots defined by $C$ and its
superclasses.  At most one slot of a given name can be accessible in an
instance.

In the simplest case, only one class among $C$ and its superclasses
defines a slot with a given slot name.  If a slot is defined by a
superclass of $C$, we say that the slot is inherited.  The characteristics
of the slot are determined by the slot specifier of the defining class.
Consider the defining class for a slot $S$.  If the {\bf :allocation} slot
option is omitted or its value is {\bf :instance}, then $S$ is a local
slot and each instance of $C$ has its own slot named $S$ that stores its
own value.  If the value of the {\bf :allocation} slot option is {\bf
:class}, then $S$ is a shared slot, the class that defined $S$ stores the
value, and all instances of $C$ access that single slot.

In general, more than one class among $C$ and its superclasses can define
a slot with a given name.  In such cases, only one slot with the given
name is accessible in an instance of $C$, and the characteristics of that
slot are a combination of the several slot specifiers, computed as
follows:

\beginlist

\item{\bull} All the slot specifiers for a given slot name are ordered
from most specific to least specific, according to the order in the class
precedence list of $C$ of the classes that define them.

\item{\bull} The allocation of a slot is controlled by the most specific
slot specifier.  If the most specific slot specifier does not contain an
{\bf :allocation} slot option, {\bf :instance} is used.  Less specific
slot specifiers never affect the allocation.

\item{\bull} The effective value for the {\bf :initform} option of a slot
is controlled by the most specific slot specifier that contains an {\bf
:initform} slot option.  If no slot specifier contains an {\bf :initform}
slot option, the slot has no default initial value form.

\item{\bull}
The {\bf :type} option for $C$ is the value $T\sub 1$, and
the contents of the slot $S$ will always be of type
{\tt (and}~$T\sub 1$~$\ldots$~$T\sub n${\tt )}.

\item{\bull} The contents of a slot will always be of type {\tt
(and}~$T\sub 1$~$\ldots$~$T\sub n${\tt )} where $T\sub 1 \ldots T\sub n$ are
the values of the {\bf :type} slot options contained in all of the slot
specifiers.  If no slot specifier contains {\bf :type} slot option, the
contents of a slot will always be of type {\bf t}.

\endlist

The {\bf :reader} and {\bf :accessor} slot options create methods rather
than defining characteristics of a slot. Reader and accessor
methods are inherited in the sense described in the section ``Inheritance
of Methods.''

A consequence of the allocation rule is that a shared slot can be
shadowed.  For example, if a class $C\sub 1$ defines a slot named $S$
whose value for the {\bf :allocation} slot option is {\bf :class}, that
slot is accessible in instances of $C\sub 1$ and all of its subclasses.
However, if $C\sub 2$ is a subclass of $C\sub 1$ and also defines a slot
named $S$, $C\sub 1$'s slot is not shared by instances of $C\sub 2$ and
its subclasses.  See the slot named S2 in the class named C2 in the
section ``Examples of Inheritance.''

A consequence of the type rule is that the value of a slot satisfies the
type constraint of each slot specifier that contributes to that slot.
Note that an implementation may or may not choose to check the type of
the new value when initializing or assigning to a slot.

Methods that access slots know only the name of the slot and the type of
the slot's value.  Suppose a superclass provides a method that expects
to access a shared slot of a given name and a subclass defines a local
slot with the same name.  If the method provided by the superclass is
used on an instance of the subclass, the method accesses the local slot.

\beginsubSection{Examples of Inheritance}

\screen!

(defclass C1 () 
    ((S1 :initform 5.4 :type number) 
     (S2 :allocation :class))

(defclass C2 (C1) 
    ((S1 :initform 5 :type integer)
     (S2 :allocation :instance)
     (S3 :accessor C2-S3))
  (:reader-prefix C2-))
\endscreen!

Instances of the class {\tt C1} have a local slot named {\tt S1}, whose default
initial value is 5.4 and whose value will always be a number.
{\tt C1} also has a shared slot named {\tt S2}.

There is a local slot named {\tt S1} in instances of {\tt C2}.  The
default initial value of {\tt S1} is 5.  The value of {\tt S1} will be
of type {\tt (and integer number)}.  There are also local slots named
{\tt S2} and {\tt S3} in instances of {\tt C2}.  {\tt C2} has methods
defined for reading the value of its slots; these methods are for the
generic functions named {\tt C2-S1}, {\tt C2-S2}, and {\tt C2-S3}.
There is also a method for {\bf setf} of {\tt C2-S3} that writes the
value of {\tt S3}.

\endsubSection%{Examples of Inheritance}
\endSection%{Inheritance}

\beginSection{Redefining Classes}  

When a {\bf defclass} form is evaluated and a class with the given
name already exists, the existing class is redefined.  Redefining a
class modifies the existing class object to reflect the new class
definition; it does not create a new class object for the class.  Any
method created by an {\bf :accessor}, {\bf :reader}, {\bf
:accessor-prefix}, or {\bf :reader-prefix} option specified by the old
{\bf defclass} form is removed from the corresponding generic
function unless that same method is specified by the new {\bf
defclass} form; any function specified by the {\bf :constructor}
option of the old {\bf defclass} form is removed from the
corresponding symbol function cell.   Let $C$ be the class being
redefined, and let $M\sub C$ be the set of methods removed. When $C$
is redefined, an obsolete copy of the old class is made for use during
the process of updating the instances of $C$. Call the obsolete copy
$C\sub o$.  The class $C\sub o$ has no name, and it has no instances except
during a particular part of the process of updating instances.  

When the class $C$ is redefined, changes are propagated to instances
of it and to instances of any of its subclasses.  The updating of an
instance whose class has been redefined (or any of whose superclasses
have been redefined) occurs at an implementation-dependent time, but
will usually be upon the next access to that instance or the next time
that a generic function is applied to that instance.  In this context,
an instance is said to be {\bit accessed\/} when a generic function is
called with the instance as an argument that is used for method
selection or when {\bf slot-value} is called with the instance as its
first argument.  Updating an instance does not change its identity as
defined by the {\bf eq} function.  The updating process may change the
slots of that particular instance, but it does not create a new
instance.  Whether updating an instance consumes storage is
implementation dependent.

If a class is redefined in such a way that the set of local slots
accessible in an instance of the class is changed or the order of
slots in storage is changed, the function {\bf change-class} is called
whenever an instance of the class is updated.  Implementations may
choose to invoke {\bf change-class} under other circumstances as well.
The function {\bf change-class} always calls {\bf class-changed} to
complete the transformation from the old representation of the
instance to the new representation. The generic function {\bf
class-changed} is provided to allow programmers to specify actions to
be taken when an instance is updated.  

Because the class $C\sub o$ does not have a name, any method for {\bf
class-changed} that is specialized to a particular $C\sub o$ must be
written using the functional interface, that is, by using {\bf
add-method} rather than by using {\bf defmethod}.  See the section
``Introduction to Methods.''

Note that redefining a class may cause slots to be added or deleted.
When an instance is updated,  new slots are initialized and the
values of deleted slots are discarded.  Each local slot of the new
version of the class with no slot by the same name in the old version
of the class is initialized to the value of the corresponding {\bf
:initform} option of the new class or remains uninitialized if the new
version of the class does not specify or inherit the {\bf :initform} option for
that slot.  This is the same as the initialization
done by {\bf make-instance} except that no initialization methods are
invoked and no {\bf make-instance} initialization arguments are
present.

\eject
If in the new version of the class there is a local slot of the same
name as any slot in the old version of the class, the value of that
slot is unchanged.  This means that if the slot
has a value, the value returned by {\bf slot-value} after {\bf
change-class} is invoked is {\bf eql} to the value returned by {\bf
slot-value} before {\bf change-class} is invoked.  Similarly, if the
slot was uninitialized, it remains uninitialized.  If in the new
version of the class there is a shared slot of the same name as any
shared slot in the old version of the class, the value of that slot
will be the same in both.  If in the new version of the class there is
a shared slot of the same name as any local slot in the old version of
the class, that shared slot is initialized to the value of the
corresponding {\bf :initform} option of the new class or remains
uninitialized if the new version of the class does not specify or
inherit the {\bf :initform} option for that slot.

After {\bf change-class} has completed the above operations, it invokes
the generic function {\bf class-changed} on two arguments computed by
{\bf change-class}. The first argument passed is a copy of the instance
being updated and is an instance of the obsolete class $C\sub o$; call
this instance $I\sub o$.  The second argument is the instance as updated
so far by {\bf change-class} and is an instance of the class $C$. The
methods $M\sub C$, which were removed by the redefinition of the class $C$,
apply to instances of $C\sub o$; for example, they apply to $I\sub o$.
The methods defined on {\bf class-changed} can use the methods in $M\sub
C$---by invoking the appropriate generic functions---to obtain
information that is not directly stored in $I\sub o$. $I\sub o$ is
constrained to have dynamic extent, so referencing it outside of the
dynamic extent of {\bf class-changed} is an error. Note that $C\sub o$
has an instance within the dynamic extent of {\bf class-changed}; this
is the only time that any instances of $C\sub o$ will exist.

The \CLOS\ guarantees that {\bf defclass} can be used to change the
definition of an existing class that was previously defined by {\bf
defclass} as long as the {\bf :metaclass} option is not used in either
the old or the new definition.  Whether {\bf defclass} is allowed to
change the metaclass and whether redefining a class causes existing
instances to be updated is up to the implementor of the particular
metaclass.  ``The \CLOS\ Meta-Object Protocol'' will describe how to
control this.

\endSection%{Redefining Classes}

\beginSection{Integrating Types and Classes} 

The \CLOS\ maps the Common Lisp type space into the space of classes.
Every class that has a proper name has a corresponding type with the same 
name.  The {\bf defclass} and {\bf defstruct} constructs define both
types and classes.  

The proper name of every class is a valid type specifier.   In addition, every
class object is a valid type specifier.  Thus the expression {\tt (typep 
{\it object class\/})} evaluates to true if the class of {\it object\/} 
is {\it class\/} itself or a subclass of {\it class}.  The evaluation of
the expression {\tt (subtypep {\it class1 class2\/})} returns the
values {\bf t t} if {\it class1\/} is a subclass of {\it class2\/} or if they
are the same class; otherwise it returns the values {\bf nil t}. 
If $I$ is an instance of some class $C$
named $S$, the evaluation of the
expression {\tt (type-of $I$)} will return $S$ if $S$ is the proper
name of $C$, otherwise it will return $C$.

Many but not all of the predefined Common Lisp type specifiers have a
corresponding class with the same proper name as the type.  For 
example, the type {\bf array} has a corresponding class named {\bf array}.  
A class that corresponds to a predefined Common Lisp type is called a
{\bit standard type class\/}.  Each standard type class has the class
{\bf standard-type-class} as a metaclass.  It is not allowed to make an
instance of a standard type class with {\bf make-instance} or to include
a standard type class as a superclass of a class.

The purpose for specifying that many of the standard Common Lisp types
have a corresponding class is to allow users to write methods that
discriminate on these types.  The hierarchical relationships among   
the Common Lisp types are maintained by the classes corresponding to  
those types.   Thus the existing type hierarchy is used for determining  
the class precedence lists for each standard type class.    

Method selection requires that a class precedence list can be
determined for each class.  This list orders the class and its superclasses
from  most to least specific.  In some cases, {\it Common Lisp: The 
Language\/} does not specify a subtype/supertype relationship for two 
supertypes of a given type.   For example, {\bf null} is a subtype of
both {\bf symbol} and {\bf list}, but {\it Common Lisp: The Language\/} 
does not specify whether {\bf symbol} is more or less specific than {\bf
list}.  The \CLOS\ specification defines those relationships for all
standard type classes. 

The following table lists the set of standard type classes required by
\CLOS.  The superclasses of each standard type class are presented in
order from most specific to most general.

\boxfig
{\dimen0=.75pc
\tabskip \dimen0 plus .5 fil
\halign to \hsize {#\hfil\tabskip \dimen0 plus 1fil&#\hfil\tabskip \dimen0 plus .5 fil&&#\hfil\cr  %was &&#
\noalign{\vskip -9pt}
\hfil\bf Standard Type Class&\hfil\bf Superclasses\span\omit\span\omit\cr
\noalign{\vskip 2pt\hrule\vskip 2pt}
array&t\cr
bit-vector&vector, array, sequence, t\cr
character&t\cr
complex&number, t\cr
cons&list, sequence, t\cr
float&number, t\cr
integer&rational, number, t\cr
list&sequence, t \cr
null&list, symbol, sequence, t\cr
number&t\cr
ratio&rational, number, t\cr
rational&number, t\cr
sequence&t\cr
string&vector, array, sequence, t\cr
symbol&t\cr
t\cr
vector&array, sequence, t\cr
\noalign{\vskip -9pt}
}}
\caption{}
\endfig
 
Note that instances of standard classes are type disjoint with all other
types.

Individual implementations can allow other type specifiers to have a 
corresponding class.  Individual implementations can also add additional
subclass relationships as long as they do not violate {\it Common Lisp:
the Language\/}.  

Creating a type by means of {\bf defstruct} also creates a class in the
space of Common Lisp classes.  Such a class is an instance of {\bf
structure-class} and a direct subclass of the class that corresponds to
the included structure, if any.

No type specifier that is a list, such as {\tt (vector double-float 
100)}, has a corresponding class.   No type defined by {\bf deftype} has 
a corresponding class. 

%For a discussion on some of the design decisions underlying this aspect
%of \CLOS\, see the section ``Design Theories of the Integration of Types
%and Classes''.

\endSection%{Integrating Types and Classes}

\beginSection{Determining the Class Precedence List}

The {\bf defclass} form for a class provides a total ordering on that
class and its direct superclasses.  This ordering is called the {\bit
local precedence order\/}.  It is an ordered list of the class and its
direct superclasses. A class precedes its direct superclasses, and a
direct superclass precedes all other direct superclasses specified to
its right in the superclasses list of the {\bf defclass} form.  For
every class $C$ we define $$R\sub C=\{(C,C\sub 1),(C\sub 1,C\sub
2),\ldots,(C\sub {n-1},C\sub n)\}$$ where $C\sub 1,\ldots,C\sub n$ are
the direct superclasses of $C$ in the order in which they are mentioned in the
{\bf defclass} form. These ordered pairs generate the total ordering on
the class $C$ and its direct superclasses.

Let $S\sub C$ be the set of $C$ and its superclasses. Let $R$ be
$$R=\bigcup\sub{c\in {S\sub C}}R\sub c$$

$R$ may or may not generate a partial ordering, depending on whether the
$R\sub c$, $c\in S\sub C$, are consistent; we assume they are consistent
and that $R$ generates a partial ordering. When the $R\sub c$ are not
consistent we say that $R$ is inconsistent.
This partial ordering is generated 
by taking the
the transitive closure
of the set $R\cup \{(c,c) \vert c\in {S\sub C}\}$.
When $(C\sub 1,C\sub 2)\in R$, we say that $C\sub 1$ {\bit
precedes} $C\sub 2$.

To compute the class precedence list at~$C$, we topologically sort the
elements of $S\sub C$ with respect to the partial ordering generated
by $R$.  When the topological sort must select a class from a set of
two or more classes, none of which are preceded by other classes with
respect to~$R$, the class selected is chosen deterministically, as
described below.

We require that an implementation of \CLOS\ signal an error if 
$R$ is inconsistent, that is, if the class precedence list cannot be
computed.

\beginsubSection{Topological Sorting}

Topological sorting proceeds by finding a class $C$ in~$S\sub C$
such that no other class precedes that element according to the
elements in~$R$.  $C$ is placed first in the result.  We remove $C$ from
$S\sub C$, and we remove all pairs of the form $(C,D)$,
$D\in S\sub C$, from $R$. We repeat the process, adding
classes with no predecessors at the end of the result.  We stop when
no element can be found that has no predecessor.

If $S\sub C$ is not empty and the process has stopped, the
set $R$ is inconsistent: if every class in the finite set of classes
is preceded by another, then $R$ contains a loop, and there
are two classes, $C\sub 1$ and $C\sub 2$, such that $C\sub 1$ precedes
$C\sub 2$ and $C\sub 2$ precedes $C\sub 1$.

\eject
Sometimes there are several classes from $S\sub C$ with no
predecessors.  In this case we select the one that has a direct
subclass rightmost in the class precedence list computed so far.
Because a direct superclass precedes all other direct superclasses to
its right, there can be only one such candidate class. If there are no
such candidate classes, $R$ does not generate a partial ordering---the
$R\sub c$, $c\in S\sub C$, are inconsistent.

In more precise terms, let $\{N\sub 1,\ldots,N\sub m\}$, $2\leq m$, be
the classes from $S\sub C$ with no predecessors.  Let $(C\sub
1\ldots C\sub n)$, $1\leq n$, be the class precedence list
constructed so far.  $C\sub 1$ is the most specific class and $C\sub
n$ is the least specific.  Let $1\leq j\leq n$ be the largest number
such that $\exists \thinspace i$ where $1\leq i\leq m$ and $N\sub i$
is a direct superclass of $C\sub j$; $N\sub i$ is placed next.

The effect of this rule for selecting from a set of classes with no
predecessors is that simple superclass chains and relatively separated
subgraphs are kept together in the class precedence list. For example,
let $T\sub 1$ and $T\sub 2$ be subgraphs whose only element in common is
the class {\bf t}; let $C\sub 1$ be the bottom of $T\sub 1$; and let
$C\sub 2$ be the bottom of $T\sub 2$. Suppose $C$ is a class whose direct
superclasses are $C\sub 1$ and $C\sub 2$ in that order, then the class
precedence list for $C$ will start with $C$ and will be followed by all
classes in $T\sub 1$; after all the classes of $T\sub 1$ will be all
classes in $T\sub 2$.

\endsubSection%{Topological Sorting}

\beginsubSection{Examples}

Here is an example of determining a class precedence list.  The classes
are defined:

\screen!

(defclass pie (apple cinnamon) ())

(defclass apple (fruit) ())

(defclass cinnamon (spice) ())

(defclass fruit (food) ())

(defclass spice (food) ())

(defclass food () ())
\endscreen!

The set $S$~$=$ $\{${\tt pie, apple, cinnamon, fruit, spice, food, t}$\}$. The
set $R$~$=$ $\{${\tt (pie, apple),
(apple, cinnamon), (apple, fruit), (cinnamon, spice),
(fruit, food), (spice, food), (food t)}$\}$.

The class {\tt pie} is not preceded by anything, so it comes first;
the result so far is {\tt (pie)}.  We remove {\tt pie} from $S$ and
pairs mentioning {\tt pie} from $R$ and get $S$~$=$ $\{${\tt
apple, cinnamon, fruit, spice, food, t}$\}$ and $R$~$=$ $\{${\tt
(apple, cinnamon), (apple, fruit), (cinnamon, spice),
(fruit, food), (spice, food), (food t)}$\}$.

\eject
The class {\tt apple} is not preceded by anything, so it is next; the
result is {\tt (pie apple)}. Removing {\tt apple} and the relevant
pairs we get $S$~$=$ $\{${\tt cinnamon, fruit, spice, food, t}$\}$ and
$R$~$=$ $\{${\tt (cinnamon, spice), (fruit, food),
(spice, food), (food t)}$\}$.

The classes {\tt cinnamon} and {\tt fruit} are not preceded by
anything, so we look at which of these two has a direct subclass
rightmost in the class precedence list computed so far.  The class
{\tt apple} is a direct subclass of {\tt fruit} and is rightmost in
the precedence list.  Therefore, we select {\tt fruit} next, and the
result so far is {\tt (pie apple fruit)}.  $S$~$=$ $\{${\tt cinnamon,
spice, food, t}$\}$; $R$~$=$ $\{${\tt (cinnamon, spice), (spice,
food), (food t)}$\}$.

The class {\tt cinnamon} is next, giving the result so far as {\tt (pie apple
fruit cinnamon)}.  $S$~$=$ $\{${\tt spice, food, t}$\}$; $R$~$=$
$\{${\tt (spice, food), (food t)}$\}$.

The classes {\tt spice}, {\tt food}, and {\tt t} are added in that
order, and the class precedence list is {\tt (pie apple fruit cinnamon
spice food t)}.

It is possible to write a set of class definitions that cannot be 
ordered.   For example: 

\screen!

(defclass new-class (fruit apple) ())

(defclass apple (fruit) ())
\endscreen!

The class {\tt fruit} must precede {\tt apple} because the local
ordering of superclasses is preserved.  The class {\tt apple} must
precede {\tt fruit} because a class always precedes its own
superclasses.  When this situation occurs, an error is signaled when
the system tries to compute the class precedence list.

Note the following example, which appears at first glance to be a
conflicting set of definitions: 

\screen!

(defclass pie (apple cinnamon) ())

(defclass pastry (cinnamon apple) ())

(defclass apple () ())

(defclass cinnamon () ())
\endscreen!

The class precedence list for {\tt pie} is  {\tt (pie apple cinnamon t)}.

The class precedence list for {\tt pastry} is  {\tt (pastry cinnamon apple t)}.

There is no problem with the fact that {\tt apple} precedes {\tt
cinnamon} in the ordering of the superclasses of {\tt pie} but does not in the
ordering for {\tt pastry}.  However, it is not possible to build a new class
that has both {\tt pie} and {\tt pastry} as superclasses.

\endsubSection%{Examples}

\endSection%{Determining the Class Precedence List}



\beginSection{Generic Functions and Methods}

\beginsubSection{Introduction to Generic Functions}

A generic function object comprises a set of methods, a
lambda-list, a method combination type, and other information.

Like an ordinary Lisp function, a generic function takes arguments,
performs a series of operations, and perhaps returns useful values.  An
ordinary function has a single body of code that is always executed
when the function is called.  A generic function might perform a
different series of operations and combine the results of the
operations in different ways, depending on the class or identity of
one or more of its arguments.  A generic function can have several
methods associated with it, and the class or identity of each
argument to the generic function indicates which method or
methods to use.

Ordinary functions and generic functions are called with identical
syntax.
 
Generic functions are true functions that can be passed as arguments and
used as the first argument to {\bf funcall} and {\bf apply}.

Ordinary functions have a definition that is in one place; generic 
functions have a distributed definition.  The definition of a generic
function can be found in a set of {\bf defmethod} forms, possibly along
with a {\bf defgeneric} form that provides information about the
behavior of the generic function.  Evaluating these forms produces a
generic function object.  

In Common Lisp, a name can be given to a function in one of
two ways: a {\bit global\/} name can be given to a function using
the {\bf defun} construct; a {\bit local\/} name can be given
using the {\bf flet} or {\bf labels} special forms.
A generic function can be given a global name using the
{\bf defmethod} or {\bf defgeneric} constructs.
A generic function can be given a local name using the 
{\bf generic-flet}, {\bf generic-labels}, or {\bf with-added-methods}
special forms.

The {\bf generic-flet} special form creates a new local generic function
with the set of methods specified by its method definitions.  The scoping
of generic function names within a {\bf generic-flet} is the same as for
{\bf flet}.

The {\bf generic-labels} special form creates a new local generic function
with the set of methods specified by its method definitions.  The scoping
of generic function names within a {\bf generic-labels} is the same as for
{\bf labels}.

The {\bf with-added-methods} special form creates a new local generic
function by adding the set of methods specified by its method definitions
to the methods of the lexically visible generic function of the same name.

The {\bf generic-function} special form creates an anonymous generic
function with the set of methods specified by its method definitions.

Both {\bf defmethod} and {\bf defgeneric} use {\bf symbol-function}  
to find the generic function that they affect.   
When a generic function is associated with a symbol, that name 
is in a certain package and can be exported if it is part of an external 
interface.  

When a new {\bf defgeneric} form is evaluated and a generic
function of the given name already exists, the existing generic function
object is modified.  This does not modify any of the methods associated
with the generic function.  When a {\bf defgeneric} form is
evaluated and no generic function of the given name exists, a generic
function is created with the methods specified by its method defintions.

When a {\bf defmethod} form is evaluated and a generic function of the
given name already exists, the existing generic function object is
modified to contain the new method.  The lambda-list of the new method
must be congruent with the lambda-list of the generic function.

When a {\bf defmethod} form is evaluated and no generic function
with that name exists, a generic function is created with default
values for the argument precedence order, the generic function class,
the method class, and the method combination type.  The lambda-list of
the generic function is congruent with the lambda-list of the new method.

For a discussion of {\bit congruence}, see the section ``Congruent
Lambda-lists for All Methods of a Generic Function.''

\endsubSection%{Introduction to Generic Functions}

\beginsubSection{Introduction to setf Generic Functions}

A {\bit setf generic function\/} is called in an expression such as the
following:\break
{\tt (setf ({\it symbol arguments}) {\it new-value})}.

One example of a setf generic function is the automatically generated  
setf function created when the {\bf :accessor} option is given to
{\bf defclass}.   The {\bf :accessor} option defines a reader generic
function of a given name.   It also defines a generic function that
is invoked when {\bf setf} is used with the reader generic function.   If the
reader generic function is named {\it ship-color\/}, the corresponding 
setf generic function is invoked by means of the expression  
{\tt (setf (ship-color {\it ship\/}){\it new-value\/})}.  

The macro {\bf defgeneric-setf} can be used to define a setf
generic function.  
The macro {\bf defmethod-setf} can be used to define a method for a setf 
generic function.  

Note that unlike other generic functions, setf generic functions do
not have names.  The macros {\bf defmethod-setf} and {\bf
defgeneric-setf} use {\bf get-setf-generic-function} to find
the generic function they affect.  

\endsubSection%{Introduction to setf Generic Functions}

\beginsubSection{Introduction to Methods}

A method object contains a method function, an ordered set of {\bit parameter
specializers\/} that specify when the given method is applicable, and
an ordered set of {\bit qualifiers\/} that are used by the method combination
facility to distinguish among methods.

The macro {\bf defmethod} is used to create a method object.  A {\bf
defmethod} form contains the code that is to be run when the
arguments to the generic function cause the method that it
defines to be selected.  If a {\bf defmethod} form is evaluated and a
method object corresponding to the given generic function name, 
parameter specializers, and qualifiers already exists, the 
new definition replaces the old. 

Each method has a {\bit specialized lambda-list}, which determines
when that method can be selected.  A specialized lambda-list is like
an ordinary lambda-list except that a {\bit specialized parameter\/}
may occur instead of the name of a parameter.  A specialized parameter
is a list, {\tt ({\it variable-name parameter-specializer-name\/})},
where {\it parameter-specializer-name\/} is a parameter specializer
name.  Every parameter specializer name is a Common Lisp type
specifier, but the only Common Lisp type specifiers that are valid as
parameter specializer names are the following: 

\beginlist

\item{\bull} The name of any class

\item{\bull} {\tt ({\bf eql} {\it object\/})}

\endlist

A parameter specializer name denotes a parameter specializer as follows:
Let $N$ be a parameter specializer name and $P$ be the corresponding
parameter specializer; if $N$ is a class name, then $P$ is the class with
that name; otherwise $N$ equals $P$.

Parameter specializer names are used in macros intended as the user-level
interface ({\bf defmethod} and {\bf defmethod-setf}), while parameter
specializers are used in the functional interface ({\bf make-method} and
{\bf get-method}).

Only required parameters can be specialized, and there must be a
parameter specializer for each required parameter.  For notational
simplicity, if some required parameter in a specialized lambda-list is
simply a variable name, its parameter specializer defaults to the
class named {\bf t}.

A method can be selected for a set of arguments when each required
argument satisfies its corresponding parameter specializer.  The
following is a definition of what it means for an argument to satisfy
a parameter specializer.

Let $\langle A\sub 1, \ldots, A\sub n\rangle$ be the required arguments
to a generic function in order. Let $\langle P\sub 1, \ldots, P\sub
n\rangle$ be the parameter specializers corresponding to the required
parameters of the method $M$ in order.  The method $M$ can be selected
when each $A\sub i$ satisfies $P\sub i$.  If $P\sub i$ is a class, and
if $A\sub i$ is an instance of a class $C$, then we say that $A\sub i$
satisfies $P\sub i$ when $C=P\sub i$ or when $C$ is a subclass of $P\sub i$.
If $P\sub i$ is {\tt ({\bf eql} {\it object})}, then we say that
$A\sub i$ satisfies $P\sub i$ when $A\sub i$ is {\bf eql} to {\it
object}.

This proposal requires that both parameter specializers and parameter
specializer names be Common Lisp type specifiers.

Because a parameter specializer is a type specifier, the function {\bf
typep} can be used to determine whether an argument satisfies a
parameter specializer during method selection.  Thus, this standard
includes an upward-compatible extension of the Common Lisp type system
and does not create another type system.  Note that in general a
parameter specializer cannot be a type specifier list, such as {\tt
({\bf vector single-float})}.   The only parameter specializer that can
be a list is {\tt ({\bf eql} {\it object\/})}.
This proposal requires that Common Lisp be modified to include 
{\tt ({\bf deftype eql} ({\it object\/}) `({\bf member} {\it ,object\/}))}.

A future extension might allow optional and keyword parameters to be
specialized.

A method all of whose parameter specializers are the class named {\bf
t} is a {\bit default method\/}; it is always applicable but often
shadowed by a more specific method.

Methods can have {\bit qualifiers}, which give the method combination
procedure a way to distinguish between methods.  A method that has one
or more qualifiers is called a {\bit qualified\/} method.
A method with no qualifiers is called an {\bit unqualified method}. 
A qualifier is any object other than a list, that is,
any non-{\bf nil} atom.  By convention, qualifiers are usually keyword
symbols---it is rare to find a vector used as a qualifier.

In this specification, the terms {\bit primary method\/} and {\bit
auxiliary method\/} are used to partition methods within
a method combination type according to their intended use.
In standard method combination, primary methods are
unqualified methods and auxiliary methods are methods with a
single qualifier that is {\bf :around}, {\bf
:before}, or {\bf :after}.  When a method combination type is defined
using the short form of {\bf define-method-combination}, primary
methods are defined to include not only the unqualified methods but
certain others as well.  

Thus, the terms {\bit primary method\/} and {\bit auxiliary method\/}
have only a relative definition within a given method combination
type.

\endsubSection%{Introduction to Methods}

\beginsubSection{Congruent Lambda-lists for All Methods of a Generic Function}

These rules define the congruence of a set of lambda-lists, including the
lambda-list of each method for a given generic function and the
lambda-list specified with {\bf defgeneric}, if present.  

These rules also apply to (SETF~{\it generic})} methods.

\beginlist

\item{1.} Each lambda-list must have the same number of required
parameters.

\item{2.} Each lambda-list must have the same number of optional
parameters.  Each method can supply a different default for an optional
parameter.

\item{3.} If any lambda-list mentions {\bf \&rest} or {\bf \&key}, each
lambda-list must mention one or both of these.

\item{4.} If the {\bf defgeneric} lambda-list mentions {\bf \&key}, each
method must accept all of the keyword names mentioned after {\bf \&key} in
{\bf defgeneric}, either by accepting them explicitly, by specifying {\bf
\&allow-other-keys}, or by specifying {\bf \&rest} but not {\bf \&key}.
Each method can accept additional keyword arguments of its own.  The
checking of the validity of keyword names is done in in the generic
function, not in each method.

\item{5.} The use of {\bf \&allow-other-keys} need not be consistent
across lambda-lists.  If {\bf \&allow-other-keys} is mentioned in any
lambda-list, then any keyword arguments may be mentioned in the call to the
generic function.

\item{6.} The use of {\bf \&aux} need not be consistent across methods.

\endlist

\endsubSection%{Congruent Lambda-lists for All Methods of a Generic Function}

\beginsubSection{Named Arguments in Generic Functions and Methods}

When a generic function or its methods mentions {\bf \&key} in a
lambda-list, the specific set of named arguments accepted by the generic
function varies depending on the applicable methods.  The named arguments
accepted by the generic function for a particular call are the union of
the named arguments accepted by any applicable method and the named
arguments mentioned after {\bf \&key} in the {\bf defgeneric} form, if
any.  There is no attempt to exclude methods that are applicable but are
not actually called.  Note that in standard method combination, all
applicable methods are potentially callable if {\bf call-next-method} is
used.  A method that has {\bf \&rest} but not {\bf \&key} does not affect
the set of acceptable named arguments.  If the lambda-list of any
applicable method or of the {\bf defgeneric} form contains {\bf
\&allow-other-keys}, all named arguments are accepted by the generic
function.

The lambda-list congruence rules require that each method accept all of
the named arguments mentioned after {\bf \&key} in the {\bf defgeneric}
form, by accepting them explicitly, by specifying {\bf
\&allow-other-keys}, or by specifying {\bf \&rest} but not {\bf \&key}.
Each method can accept additional named arguments of its own, in addition
to the named arguments mentioned by the {\bf defgeneric} form.

For example, suppose there are two methods defined for {\tt width}
as follows:

\screen!

(defmethod width ((c character) &key font) ...)

(defmethod width ((p picture) &key pixel-size) ...)
\endscreen!

\noindent Assume that there are no other methods and no {\bf defgeneric}
for {\tt width}. Then the evaluation of the following form is and error
unless {\tt x} is both a character and a picture---the acceptable
arguments are determined by the applicable methods, not by all methods.

\screen!

(width x :font 'foo :pixel-size 10)
\endscreen!

\endsubSection%{Named Arguments in Generic Functions and Methods}

\endSection%{Generic Functions and Methods}

\beginSection{Method Selection and Combination}

When a generic function is called with particular arguments, it must decide
what code to execute.  We call this code the {\bit effective method\/} for
those arguments.  The effective method can be one of the methods for the
generic function or a combination of several of them.

When the effective method has been determined, it is called with the same
arguments that were passed to the generic function.  Whatever values it
returns are returned as the values of the generic function.

Choosing the effective method involves the following decisions: 

\beginlist

\item{\bull} Which method or methods to call

\item{\bull} The order in which to call the methods

\item{\bull} Which method to call when {\bf call-next-method} is invoked

\item{\bull} Which value or values to return 

\endlist

\beginsubSection{Determining the Effective Method}

The effective method is determined by the following three-step procedure:

\beginlist

\item{1.}{Select the set of applicable methods.}

\item{2.}{Sort the applicable methods by precedence order, putting
the most specific method first.}

\item{3.}{Apply method combination to the sorted list of
applicable methods, producing the effective method.}

\endlist

\beginsubsubsection{Selecting the Set of Applicable Methods}

Given a generic function and a set of arguments, the {\bit applicable
methods\/} are all methods for that generic function whose parameter
specializers are satisfied by their corresponding arguments.

\endsubsubsection%{Selecting the Set of Applicable Methods}

\beginsubsubsection{Sorting the Applicable Methods by Precedence Order}

To compare the precedence of two methods, examine their parameter
specializers in order.  The default examination order is from left to
right, but an alternative order may be specified by the {\bf
:argument-precedence-order} option to {\bf defgeneric} or {\bf
defgeneric-setf}.

Compare the corresponding parameter specializers from each method.  When
a pair of parameter specializers are equal, proceed to the next pair and
compare them for equality.  If all corresponding parameter specializers
are equal, the two methods must have different qualifiers; in this case,
either method can be selected to precede the other.  If some
corresponding parameter specializers are not equal, the first pair of
parameter specializers that are not equal determines the precedence.

If both parameter specializers are classes, consider the class
precedence list of the class of the argument.  The more specific of
the two methods is the method whose parameter specializer appears
earlier in the class precedence list.  Because of the way in which the
set of applicable methods is chosen, the parameter specializers are
guaranteed to be present in the class precedence list of the class of
the argument.

If just one parameter specializer is {\tt ({\bf eql} {\it
object\/})}, the method with that parameter specializer precedes the
other method.  If both parameter specializers are {\bf eql}
forms, the
specializers must be equal (otherwise the two methods would
not both have been applicable for this argument).

The resulting list of applicable methods has the most specific
method first and the least specific method last.    

\endsubsubsection%{Sorting the Applicable Methods by Precedence Order}

\beginsubsubsection{Applying Method Combination to the Sorted List of Applicable Methods}

In the simple case---if standard method combination is used and all
applicable methods are primary methods---the effective method is the
most specific method.  That method can call the next most specific
method by using the function {\bf call-next-method}.  The method that
{\bf call-next-method} will call is referred to as the {\bit next method}.

In general, the effective method is some combination of the applicable
methods.  It is defined by a Lisp form that contains calls to some or
all of the applicable methods, returns the value or values to be
returned by the generic function, and optionally makes some of the
methods accessible by means of {\bf call-next-method}.  This Lisp form
is the body of the effective method; it is augmented with an
appropriate lambda-list to make it a function.

Method qualifiers determine the role of each method in the effective
method.  The meaning of the qualifiers of a method is defined entirely by
this step of the procedure.  If an applicable method has an unrecognized
qualifier, this step reports an error and does not include that method in
the effective method.

When standard method combination is used together with qualified methods, 
the effective method is produced as described in the section
``Standard Method Combination.''

The programmer can select another type of method combination by using the
{\bf :method-combination} option of {\bf defgeneric}.  This allows
the programmer to customize this step of this procedure without having to 
consider what happens in the other steps.

New types of method combination can be defined using the 
{\bf define-method-combination} macro.  The body of the 
{\bf define-method-combination} returns the Lisp form that defines the
effective method.

The meta-object level also offers a mechanism for defining new types
of method combination.  The generic function {\bf
compute-effective-method} receives as arguments the generic function,
the sorted list of applicable methods, the name of the method
combination type, and the list of options specified in the {\bf
:method-combination} option of {\bf defgeneric}.  It returns
the Lisp form that defines the effective method.  The programmer can
define a method for {\bf compute-effective-method} directly by using
{\bf defmethod} or indirectly by using {\bf define-method-combination}.

\endsubsubsection

\beginImplNote
In the simplest implementation, the generic function would compute the
effective method each time it was called.  In practice, this might be
too inefficient for most implementations.  Instead, these
implementations might employ a variety of optimizations of the
three-step procedure, such as precomputation into tables, compilation,
and/or caching to speed things up.  Some illustrative examples of
such optimizations are the following:

\beginlist

\item{\bull} Use a hash table keyed by the class of the arguments to
store the effective method.

\item{\bull} Compile the effective method and save the resulting
compiled function in a table.

\item{\bull} Recognize the Lisp form as an instance of a pattern of
control structure and substitute a closure that implements
that structure.

\item{\bull} Examine the parameter specializers of all methods for the
generic function and enumerate all possible effective methods.
Combine the effective methods, together with code to select from
among them, into a single function and compile that function.  Call
that function whenever the generic function is called.
\endlist
\endImplNote

The Lisp form computed by Step~3 as the body of the effective method serves
as a more general interface.  For example, a tool that determines which
methods are called and presents them to the user works by going through the
first three steps of the above procedure and then by analyzing the form to
determine which methods it calls instead of by evaluating it.

Separating the procedure of determining the effective method from the
procedure of invoking methods and combining their results, and using a Lisp
form as the interface between these procedures, allows for more optimizations
to the speed of the code and also enables more powerful programming tools
to be written.


\endsubSection%{Determining the Effective Method}

\vfill\eject
\beginsubSection{Standard Method Combination}

Standard method combination is used if no other type of
method combination is specified.   Standard method combination 
recognizes four roles for methods, as determined by method qualifiers.   

{\bit Primary methods\/} define the main action of the effective method,  
while {\bit auxiliary methods\/} modify that action in one of three ways.
A primary method has no method qualifiers.

The auxiliary methods are {\bf :before}, {\bf :after}, and {\bf :around}
methods.  

\beginlist

\item{\bull}
A {\bf :before} method has the keyword {\bf :before} as its
only qualifier.  A {\bf :before} method specifies code that is to be
run before the primary method.

\item{\bull}
An {\bf :after} method has the keyword {\bf :after} as its only
qualifier.  An {\bf :after} method specifies code that is to be run
after the primary method.  

\item{\bull}
An {\bf :around} method has the keyword {\bf :around} as its only
qualifier.

\endlist

The semantics of standard method combination are:

\beginlist

\item{\bull} If there are any {\bf :around} methods, the most specific
{\bf :around} method is called.  It supplies the value or values of the
generic function.

\item{\bull} 
Inside the body of an {\bf :around} method, {\bf call-next-method} can
be used to immediately call the next method.  When the next method
returns, the {\bf :around} method can execute more code, perhaps based
on the returned value or values.  By convention, {\bf :around} methods
almost always use {\bf call-next-method}.

\item{\bull} 
If an {\bf :around} method invokes {\bf call-next-method}, the next
most specific {\bf :around} method is called, if one is applicable.
If there are no {\bf :around} methods or if {\bf
call-next-method} is called by the least specific {\bf :around}
method, the other methods are called as follows:

\itemitem{--} All the {\bf :before} methods are called, in
most specific first order.  Their values are ignored.

\itemitem{--} 
The most specific primary method is called.  Inside the body of a
primary method, {\bf call-next-method} may be used to pass control
to the next most specific primary method.  When that method returns,
the first primary method can execute more code, perhaps based on the
returned value or values.  An error is signaled if {\bf
call-next-method} is used and there is no applicable primary method to
call.  If {\bf call-next-method} is not used, only the most specific
primary method is called.


\itemitem{--} All the {\bf :after} methods are called in
most specific last order.  Their values are ignored.


\item{\bull}
If no {\bf :around} methods were invoked, the most specific primary
method supplies the value or values returned by the generic function.
Otherwise, the value or values returned by the most specific primary
method are those returned by the invocation of
{\bf call-next-method} in the least specific {\bf :around} method.

\endlist

In standard method combination, if there are any applicable methods at
all, then there must be an applicable primary method.  In cases where
there are applicable methods, but no primary method, an error is
signaled.

An error is signaled if {\bf call-next-method} is used and there is no
next method remaining.

An error is signaled if {\bf call-next-method} is used in a {\bf :before}
or {\bf :after} method.

Standard method combination allows no more than one qualifier per method.

Running {\bf :before} methods in most specific first order while
running {\bf :after} methods in least specific first order provides a
degree of transparency.  If class $C \sub 1$ modifies the behavior of
its superclass, $C \sub 2$, by adding an auxiliary method, the
partitioning of $C \sub 2$'s behavior into primary, {\bf :before}, and
{\bf :after} methods is transparent.  Whether class $C \sub 2$ defines
these methods directly or inherits them from its superclasses is
transparent.  Class $C \sub 1$'s {\bf :before} method runs before
all of class $C \sub 2$'s methods.  Class $C \sub 1$'s {\bf :after}
method runs after all of class $C \sub 2$'s methods.

The {\bf :around} methods are an exception to this rule; they do not combine
transparently.  All {\bf :around} methods run before any other methods
run.  Thus, a less specific {\bf :around} method runs before a more specific
primary method.

If only primary methods are used, standard method combination behaves like
CommonLoops.  If {\bf call-next-method} is not used, only the most specific
method is invoked; that is, more general methods are shadowed by more
specific ones.  If {\bf call-next-method} is used, the effect is the same
as {\bf run-super} in CommonLoops.

If {\bf call-next-method} is not used, standard method combination behaves
like {\bf :daemon} method combination of New Flavors, with {\bf :around}
methods playing the role of whoppers, except that the ability to reverse
the order of the primary methods has been removed.

\endsubSection%{Standard Method Combination}



\beginsubSection{Declarative Method Combination}

The programmer can define new forms of method combination by using
the {\bf define-method-combination} macro.  This allows customization
of Step~3 of the method combination procedure described in the
section ``Determining the Effective Method.''  There are two forms
of {\bf define-method-combination}.  The short form is a simple
facility for the cases that have been found to be
most commonly needed.
The long form is more powerful but more verbose.  It resembles
{\bf defmacro} in that the body is an expression that computes
a Lisp form, usually using backquote.  Thus, arbitrary control 
structures can be implemented.  The long form also allows arbitrary
processing of method qualifiers.
The syntax and use of both forms of {\bf define-method-combination} is
explained in the second chapter of this document.

\endsubSection%{Declarative Method Combination}
\endSection%{Method Selection and Combination}


\beginSection{Meta Objects}

\beginsubSection{Metaclasses}

The {\bit metaclass\/} of an object is the class of its class.  The
metaclass determines the form of inheritance used by its classes and the
representation of the instances of its classes.  The metaclass mechanism
can be used to provide particular forms of optimization or to tailor the
\CLOS\ for particular uses (such as the implementation of other object
languages like Smalltalk-80, Loops, and CommonObjects).

Any new metaclass must define the structure of its instances, how their
storage is allocated, how their slots are accessed, and how slots and
methods are inherited.  The protocol for defining metaclasses will be
discussed in Chapter~3, ``The \CLOS\ Meta-Object Protocol.''

\endsubSection

\beginsubSection{Standard Metaclasses}

The \CLOS\ provides a number of predefined metaclasses.  These
include the following: {\bf standard-class}, 
{\bf standard-type-class}, and {\bf structure-class}.

\beginlist

\item{\bull}
The class {\bf standard-class} is the default class of classes defined
by {\bf defclass}.

\item{\bull}
The class {\bf standard-type-class} is a metaclass of all the classes 
that correspond to the standard Common Lisp types specified in
{\it Common Lisp: The Language\/} by Guy L. Steele Jr. 
%These types are listed in Figure~1-1. 
It is not allowed to make an instance of a standard type class by using 
{\bf make-instance}, or to use a standard type class
as a superclass of a user-defined class. 
It is still under discussion which Common Lisp types will have corresponding
classes.

\item{\bull}
The class {\bf structure-class} is a subclass of {\bf standard-type-class}.  
All classes defined by means of {\bf defstruct} are instances of 
{\bf structure-class} or a subclass of {\bf structure-class}.

\endlist

\endsubSection%{Standard Metaclasses} 

\beginsubSection{Standard Meta-Objects}

The \CLOS\ provides the predefined meta-objects
{\bf standard-method} and {\bf standard-generic-function}. 

\beginlist

\item{\bull}
The class {\bf standard-method} is the default class of methods
defined by {\bf defmethod} or {\bf defmethod-setf}.

\item{\bull}
The class {\bf standard-generic-function} is the default class of 
generic functions defined by {\bf defmethod}, {\bf defmethod-setf},
{\bf defgeneric}, or {\bf defgeneric-setf}.

\endlist

The \CLOS\ also provides the standard method combination type, which is 
not implemented as a meta-object, but as a method. 

\endsubSection%{Standard Meta-Objects} 

\endSection%{Meta-Objects}

\beginSection{Object Creation and Initialization}

The generic function {\bf make-instance} creates and returns a new
instance of a class.  The first argument is a class or the name of a
class, and the remaining arguments are an {\bit initialization argument}
({\bit initarg}) list.  

Initialization consists of several distinct steps, including:  combining
the explicitly supplied initargs with default values for the
unsupplied initargs, checking the validity of the initargs, allocating
storage for the instance, filling slots with values, and executing
user-supplied methods which perform additional initialization.  The \OS\
defines {\bf make-instance} in a procedural way: each step is represented by
a generic function.  This provides a mechanism for to customizing each
step.  In addition, {\bf make-instance} is a generic function
and can be customized.

The \OS\ specifies default methods for each step, so there is well-defined
standard behavior for the entire initialization procedure.  The standard
behavior provides four simple mechanisms for controlling
initialization:

\beginlist

\item{\bull} Declaring a symbol to be an initarg for a slot, by 
   by using the {\bf :initarg} slot option. This allows one to
   provide a value for a slot in a call to {\bf make-instance}.  

\item{\bull} Supplying a default value form for an initarg, by using the
   {\bf :default-initargs} class option.   This default value is used if the
   initarg is not explicitly provided as an argument to {\bf make-instance}.

\item{\bull} Supplying a default value form for a slot, by using the {\bf
:initform} slot option.  This default value is stored in the slot if no
initarg associated with that slot is given as an argument to {\bf make-instance}
or defaulted by {\bf :default-initargs}.

\item{\bull} Defining methods for {\bf initialize-instance}.  The
slot-filling behavior described above is implemented by a system-supplied
default method for {\bf initialize-instance}.  Additional control over
initialization can be obtained by writing methods for {\bf
initialize-instance}.  In most cases {\bf :after} methods are appropriate
for this purpose, because they are called after the default method that
fills the slots and thus do not override the normal slot-filling behavior.

\endlist

Note that the object creation and initialization procedure can be
controlled at two different levels.   The standard behavior offers the 
four mechanisms mentioned above; this level can be considered the
Programmer Interface level.   At the meta-object level, greater control 
can be exerted
over each step of this procedure; this level can be
considered the interface for experimentation with alternative
object-oriented paradigms.

Note that the object creation and initialization procedure can be
controlled at two different levels.  The standard behavior offers the four
mechanisms mentioned above; this level can be considered the Programmer
Interface level.  At the Meta-object level, greater control can be exerted
over each step of this procedure; this level can be considered the
interface for experimentation with alternative
object-oriented paradigms.

There is one general guideline that helps distinguish between the Programmer
Interface and the Meta-object levels of programming.  To customize
behavior at the Programmer Interface level, methods 
that specialize on instances are written.  That is, the arguments that select
methods are instances.   To customize behavior at the Meta-object level,
methods that specialize on classes are written.  That is, the
arguments that select methods are classes.

\beginsubSection{Terminology Related to Object Creation and Initialization}

The terminology related to object creation and initialization is
presented here:

\beginlist

\item{\bull} {\bit Initarg}: An initarg (initialization argument) is a keyword
argument that can be used to control object creation and initialization.
The {\bf \&key} arguments to {\bf make-instance} are initargs.  It is
often convenient to use keyword symbols to name initargs, but the name of
an initarg can be any symbol, including {\bf nil}.  There are two
purposes for an initarg:  to fill a slot with a value or to provide an
argument for an initialization method.  A single initarg can be used for
more than one purpose.

\item{\bull} {\bit Initarg list}: An initarg list (initialization argument list)
is a list of alternating initarg names and values.  Its structure is
identical to a property list and also identical to the portion of an
argument list processed for {\bf \&key} parameters.  As in those lists, if
an initarg name appears more than once in an initarg list, the leftmost
occurrence supplies the value and the remaining occurrences are ignored.
The arguments to {\bf make-instance} (after the first argument) are an
initarg list.  As in an {\bf \&key} argument list, {\bf :allow-other-keys}
can appear in an initarg list, and if its value is non-{\bf nil},
error-checking of initarg names is disabled.

\item{\bull} {\bit Slot-filling initarg}: A slot-filling initarg is an initarg
associated with a slot.  If the initarg has a value in the initarg list,
the value is stored into the slot of the newly-created object, overriding
any initform associated with the slot.  A single initarg can fill more
than one slot.  A slot-filling initarg that fills a shared slot stores its
value into the shared slot, replacing any previous value.

\item{\bull} {\bit Method-implemented initarg}: A method-implemented
initarg is an initarg associated with a method.  A method-implemented
initarg is intended as an argument for one or more methods for {\bf
initialize-instance} or {\bf allocate-instance}.  When an object is
created, the method is called with the initarg's name and value as a named
argument and the method uses the value however it chooses.  If the initarg
has no value in the initarg list, the method's lambda-list supplies a
default value.

\endlist

\endsubSection%{Terminology Related to Object Creation and Initialization}

\beginsubSection{Declaring the Validity of Initargs}

The generic function {\bf make-instance} checks the validity of the
initargs and signals an error if an initarg is supplied that is not valid.
An initarg is declared as valid in the same place where its purpose
(whether slot-filling or method-implemented) is stated.

Slot-filling initargs are declared as valid by the {\bf :initarg} slot option
to {\bf defclass}.  The 
{\bf :initarg} slot option is inherited from superclasses.
Thus, the set of valid slot-filling initargs for a class is the union of
the initargs declared by the class and its superclasses.

Method-implemented initargs are declared as valid by defining methods for
{\bf initialize-instance} or {\bf allocate-instance}.  The keyword name of
each keyword parameter specifier in the method's lambda-list becomes a
method-implemented initarg for all classes for which this method is
applicable.  Thus, method inheritance controls the set of valid
method-implemented initargs.  

The set of valid initargs for a class is the union of the valid
slot-filling initargs, the valid method-implemented initargs, and the
pre-defined initarg {\bf :allow-other-keys}.  The default for {\bf
:allow-other-keys} is {\bf nil}, and its specification is the same as
Common Lisp defines for {\bf \&key} argument lists.

\endsubSection%{Declaring the Validity of Initargs}

\beginsubSection{Defaulting of Initargs}

A {\bit default value form} can be supplied for an initarg.  The way to
provide a default value form for either a slot-filling and
method-implemented initarg is to use the {\bf :default-initargs} class option.
A default value form is usually specified by a different class from the
class that declared the initarg as valid.  Thus, 
{\bf :default-initargs} is
usually used to supply a default value for an inherited initarg.

The {\bf :default-initargs} class option is inherited.   See ``Inheritance of 
Class Options.''

The {\bf :default-initargs} class option is a list of alternating initarg
names and forms.  Each form is the default value form for the
corresponding initarg.  The default value form of an initarg is used only
if that initarg does not appear in the arguments to {\bf make-instance}.
In that case, the default value form is evaluated in the lexical
environment of the {\bf defclass} form that supplied it, and the resulting
value is used as the initarg's value.  The initarg name and value are
appended to the initarg list supplied to {\bf make-instance}.  The result
is a {\bit defaulted initarg list} in which the explicitly supplied
initargs appear earlier in the list than the defaulted initargs.
Defaulted initargs are ordered according to the order in the class
precedence list of the classes that supplied the default values.

The {\bf :default-initargs} option is used only to provide default values for 
initargs; it does not declare a symbol as a valid initarg name.

There is a distinction between the purposes of {\bf :default-initargs} and
{\bf :initform}, with respect to slot-filling initargs.  The {\bf
:default-initargs} class option allows the user to give a default value
form for an initarg without knowing whether or not the initarg fills a
slot.  If that initarg is not explicitly supplied in a call to {\bf
make-instance}, the default value form is used, just as if it had been
supplied in the call.  In contrast, the {\bf :initform} slot option allows
the user to give a default initial value form for a slot.  An {\bf
:initform} is used only if no initarg associated with that slot is given
as an argument to {\bf make-instance} or defaulted by {\bf
:default-initargs}.  The two kinds of defaulting exist at different levels
of abstraction.

The \OS\ does not guarantee any given order of evaluation of
default-initarg forms and initforms.  If the order of evaluation is
important, {\bf initialize-instance} methods should be used instead.  In
most programs, the initforms and default-initarg forms are either
constants or simple forms that construct new objects; forms with
side-effects are permitted, but are not recommended.

\endsubSection%{Defaulting of Initargs}

\beginsubSection{Rules for Duplication of Initargs}
 
The following rules specify what happens when initargs are duplicated.

\beginlist

\item{\bull} The {\bf :initarg} slot option may be specified more than
once for a given slot.

\item{\bull} A single initarg can initialize more than one slot if the
same initarg name appears in more than one {\bf :initarg} slot option.

\item{\bull} It is valid for a given initarg name to be defined more than
once as a slot-filling initarg, as a method-implemented initarg, or both.

\item{\bull} If two initargs that initialize the same slot are given in
the arguments to {\bf make-instance}, the leftmost of these initargs in
the initarg list prevails, even if the two initargs have different names.
This behavior is consistent with the behavior of property lists and with the
portion of an argument list processed for {\bf \&key} parameters.

\item{\bull} If two different initargs that initialize the same slot have
default values, and neither is given explicitly in the arguments to
{\bf make-instance}, the initarg that appears in a 
{\bf :default-initargs} slot option
in the most specific class prevails, or if they appeared in the same
class, the one whose mention in :DEFAULT-INITARGS is leftmost in the
DEFCLASS form prevails.  During the defaulting of initargs, the defaults
are appended to the end of the initarg list in this order.

\item{\bull} If there are two different initargs that initialize the same
slot, and one was given explicitly in the arguments to {\bf make-instance} while
the other was defaulted using {\bf :default-initargs}, the explicit one prevails.
This follows from the previous two rules.

\item{\bull} If a slot has both an {bf :initform} and an {\bf :initarg}
slot option, and the slot-filling initarg is defaulted using {\bf
:default-initargs}, the initform is not used and is not evaluated.

\endlist


The following is an example of the above rules:

\screen!

  (defclass a () ((x :initarg a)))
  (defclass b (a) ((x :initarg b))
    (:default-initargs a 1 b 2))

                                 DEFAULTED 
  FORM                          INITARG LIST    CONTENTS OF X SLOT
  (make-instance 'b)            (a 1 b 2)               1
  (make-instance 'b 'a 3)       (a 3 b 2)               3
  (make-instance 'b 'b 4)       (b 4 a 1)               4
  (make-instance 'b 'a 1 'a 2)  (a 1 a 2 b 2)           1
\endscreen!

\endsubSection%{Rules for Duplication of Initargs}

\beginsubSection{Methods for INITIALIZE-INSTANCE }

The generic function {\bf initialize-instance} uses standard method
combination.  Methods for {\bf initialize-instance} can be defined in
order to perform any initialization that cannot be achieved with the
simple slot-filling mechanisms.

During initialization, {\bf initialize-instance} is invoked
after the following actions have been taken:

\beginlist 

\item{\bull} The defaulted initarg list is computed by combining the
supplied initarg list with any default initargs for the class.

\item{\bull} The validity of the defaulted initarg list is checked.  If
any of the initargs has not been declared as valid, an error is signaled.

\item{\bull} A blank instance is created.

\endlist

The generic function {\bf initialize-instance} is then called with the
blank instance and the defaulted initarg list.  The system-supplied
default method is a primary method that initializes the slots with values
according to the initarg list. 
This default method behaves as follows on each slot, whether shared or
local:

\beginlist

\item{\bull} If an initarg in the defaulted initarg list fills that slot,
its value is stored into the slot.  (This is true even if a 
{\bf :before} method
has modified the slot.)

\item{\bull} Otherwise, if the slot has an initform, the initform is
evaluated and the result is stored into the slot.

\item{\bull} The duplicate-resolution rules mentioned in the section
``Rules for Duplication of Initargs'' are obeyed.

\endlist

User-defined {\bf :after} methods are a good way to customize 
this step of the initialization process because they will be run
after the default activities of {\bf initialize-instance}.
Care should be taken to not supply primary methods
that override the default primary method unless the default activities
of {\bf initialize-instance} are not desired.

The \OS\ provides two functions that are useful in the bodies of {\bf
initialize-instance} methods.  The function {\bf slot-boundp} returns a
boolean value that states whether the slot has a value; this enables
writing {\bf :after} methods for {\bf initialize-instance} that initialize
slots only if they have not already been initialized.  The function {\bf
slot-makunbound} restores a slot to the uninitialized state.

Implementations are permitted to make certain optimizations of {\bf
initialize-instance}.  The description of {\bf initialize-instance} in
Chapter~2 mentions the possible optimizations.  One possible optimization
has the following impact on user-supplied methods:  {\bf :before} and {\bf
:around} methods for {\bf initialize-instance} cannot rely on all the
slots being uninitialized.

\endsubSection%{Methods for INITIALIZE-INSTANCE }

\beginsubSection{Procedural Definition of MAKE-INSTANCE}

The generic function
{\bf make-instance} behaves as if it were defined as follows, except that
certain optimizations are permitted: 

\screen!

(defmethod make-instance ((class standard-class) &rest initargs)
  (setq initargs (default-initargs class initargs))
  (check-initargs class initargs)  
  (let ((instance (apply #'allocate-instance class initargs)))
    (apply #'initialize-instance instance initargs)
    instance))

(defmethod make-instance ((class-name symbol) &rest initargs)
  (apply #'make-instance (symbol-class class-name) initargs))
\endscreen!

This procedure can be customized at either the Programmer Interface level,
the Meta-object level, or both.  

Customizing at the Programmer Interface level includes using the {\bf
:initform}, {\bf :initarg}, and {\bf :default-initargs} options to {\bf
defclass}, as well as defining methods for {\bf initialize-instance}.  The
Meta-object level supports extra customization by defining methods for:
{\bf default-initargs}, {\bf check-initargs}, and {\bf allocate-instance}.
Chapter~3 documents each of these generic functions and the
system-supplied default methods.

As noted above, certain optimizations of the {\bf make-instance} procedure are
permitted.  The description of {\bf initialize-instance} in Chapter~2 mentions
some possible optimizations to this procedure.   Additional
optimizations are possible, including inlining and constant-folding of
method lookup and method bodies, provided that the programming
environment either prohibits redefining these methods or updates
everything when they are redefined.  

Because of optimization, methods for the meta-object generic functions
listed may not actually be called on every call to {\bf make-instance} or may
not receive exactly the arguments that would be expected.  For example,
{\bf check-initargs} might actually be called before {\bf default-initargs} rather
than after, if it has already been determined that the default initargs
will pass {\bf check-initargs}.

\endsubSection%{Procedural Definition of MAKE-INSTANCE}

\endSection%{Object Creation and Initialization}
\endChapter
\bye